We investigate strong versions of enumeration reducibility, the most important one being s-reducibility. We prove that every countable distributive lattice is embeddable into the local structure $L(\mathfrak D_s)$ of the s-degrees. However, $L(\mathfrak D_s)$ is not distributive. We show that on $\Delta^{0}_{2}$ sets s-reducibility coincides with its finite branch version; the same holds of e-reducibility. We prove some density results for $L(\mathfrak D_s)$ . In particular $L(\mathfrak D_s)$ is upwards dense. Among the results about reducibilities that are stronger than s-reducibility, (...) we show that the structure of the $\Delta^{0}_{2}$ bs-degrees is dense. Many of these results on s-reducibility yield interesting corollaries for Q-reducibility as well. (shrink)

Let A be an infinite Δ₂⁰ set and let K be creative: we show that K≤Q A if and only if K≤Q₁ A. (Here ≤Q denotes Q-reducibility, and ≤Q₁ is the subreducibility of ≤Q obtained by requesting that Q-reducibility be provided by a computable function f such that Wf(x)∩ Wf(y)=∅, if x \not= y.) Using this result we prove that A is hyperhyperimmune if and only if no Δ⁰₂ subset B of A is s-complete, i.e., there is no Δ⁰₂ subset (...) B of A such that \overline{K}≤s B, where ≤s denotes s-reducibility, and \overline{K} denotes the complement of K. (shrink)

We use certain strong Q-reducibilities, and their corresponding strong positive reducibilities, to characterize the hyperimmune sets and the hyperhyperimmune sets: if A is any infinite set then A is hyperimmune (respectively, hyperhyperimmune) if and only if for every infinite subset B of A, one has \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\overline{K}\not\le_{\rm ss} B}$$\end{document} (respectively, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\overline{K}\not\le_{\overline{\rm s}} B}$$\end{document}): here \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\le_{\overline{\rm (...) s}}}$$\end{document} is the finite-branch version of s-reducibility, ≤ss is the computably bounded version of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\le_{\overline{\rm s}}}$$\end{document}, and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\overline{K}}$$\end{document} is the complement of the halting set. Restriction to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Sigma^0_2}$$\end{document} sets provides a similar characterization of the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Sigma^0_2}$$\end{document} hyperhyperimmune sets in terms of s-reducibility. We also show that no \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${A \geq_{\overline{\rm s}}\overline{K}}$$\end{document} is hyperhyperimmune. As a consequence, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\deg_{\rm s}(\overline{K})}$$\end{document} is hyperhyperimmune-free, showing that the hyperhyperimmune s-degrees are not upwards closed. (shrink)

We show that if M is an r‐maximal set, A is a major subset of M, B is an arbitrary set and, then. We prove that the c.e. ‐degrees are not dense. We also show that there exist infinite collections of ‐degrees and such that the following hold: (i) for every i, j,, and,(ii) each consists entirely of r‐maximal sets, and(iii) each consists entirely of non‐r‐maximal hyperhypersimple sets.

We show that the _sQ_-degree of a hypersimple set includes an infinite collection of \(sQ_1\) -degrees linearly ordered under \(\le _{sQ_1}\) with order type of the integers and each c.e. set in these _sQ_-degrees is a hypersimple set. Also, we prove that there exist two c.e. sets having no least upper bound on the \(sQ_1\) -reducibility ordering. We show that the c.e. \(sQ_1\) -degrees are not dense and if _a_ is a c.e. \(sQ_1\) -degree such that \(o_{sQ_1}, then there exist (...) infinitely many pairwise _sQ_-incomputable c.e. _sQ_-degrees \(\{c_i\}_{i\in \omega }\) such that \((\forall \,i)\;(a. (shrink)